[BAEKJOON] 17220. 마약수사대

문제 :

최근들어 세계적으로 마약과 관련한 사회적 문제들이 많이 발생하고 있다. 이에 따라 경찰은 마약 수사대의 한정된 인력이 허용하는 선에서 최대한 마약공급을 막고자 한다.

마약 공급책들은 서로에게 마약을 공급받는데, 최근 마약수사대는 마약 공급책들 간의 관계도를 일부 파악하였다. 이 관계도는 그래프로 표현될 수 있다. 각 노드는 마약 공급책, 간선은 공급 관계를 표현한다. 예를 들어 아래와 같은 그래프는 다음을 나타낸 것이다.

• 마약공급책 A가 마약 공급책 B, C, D, E 에게 마약을 공급한다.
• 마약공급책 F는 B와 C로부터 마약을 공급받아서 I에게 공급한다.
• I는 J에게, J는 K에게, D는 G에게, E는 H에게 각각 마약을 공급한다.

마약수사대는 소재를 파악하고 있는 마약 공급책을 검거할 수 있다.

예를 들어, 마약수사대가 B와 C를 검거해도 D, E, G, H는 여전히 마약을 공급받을 수 있다.

마약의 원산지는 ‘다른 공급책에게 공급받지 않으면서 마약을 공급하는 마약공급책’이다.

마약 공급책들의 관계도에 대한 정보와 마약수사대가 검거한 마약 공급책들이 주어졌을 때 여전히 마약을 공급 받을 수 있는 마약 공급책의 수를 내어주는 프로그램을 작성해보자.

입력 :

첫 번째 줄에 마약 공급책의 수 N(1 ≤ N ≤ 26)과 마약 공급책의 관계 수 M(1 ≤ M ≤ 600)이 주어진다. 각 마약 공급책은 A부터 순서대로 알파벳 대문자로 표현된다.

두번째 줄부터 M개의 줄에 각 마약 공급책의 관계가 주어진다. (A B : A -> B)

마지막 줄에 경찰이 소재를 파악하고 있는 마약 공급책들의 수와 파악중인 각 마약 공급책이 공백으로 구분되어 주어진다.

출력 :

마약수사대가 파악중인 마약 공급책을 검거한 후 여전히 마약을 공급 받는 마약 공급책의 수를 출력한다.

풀이 :

우선 접근은 빠르게 했으나 예외 케이스를 빠르게 파악하지 못해 시간이 걸린 문제였다..

실제 코딩 콘테스트에서는 이런 실수를 없애기 위해서 문제 파악부터 잘해야 할 듯 하다.

내가 놓친 포인트는 한 공급체가 반드시 한 공급체에 의해서만 공급받는 것이 아니라는 것이다.

즉 한 공급체의 공급이 끊긴다 하더라도 다른 공급체가 계속 공급되고 있다면 그 공급체는 공급받고 있는 것으로 인식시켜 줘야 한다.

이를 위해서 각 공급체 노드별로 공급받고 있는 공급체 갯수를 저장해 공급해주는 업체가 0이 되는 순가 공급이 끊기는 것으로 구현해주었다.

코드 :

#include <iostream>
#include <vector>

using namespace std;
bool *cantsupply;
int *providing;
vector<vector<int>> relation;

void blockSupply(int node) {
    cantsupply[node] = true;
    int size = relation[node].size();
    for (int i = 0; i < size; i++) {
        providing[relation[node][i]]--;
        if (providing[relation[node][i]] <= 0 && !cantsupply[relation[node][i]]) blockSupply(relation[node][i]);
    }
}

int main() {
    int n, m, ans = 0;
    char fir, sec;
    cin >> n >> m;
    cantsupply = new bool[n];
    providing = new int[n]{0};
    relation.resize(n);
    fill_n(cantsupply, n, true);
    while (m--) {
        cin >> fir >> sec;
        relation[fir - 'A'].push_back(sec - 'A');
        cantsupply[sec - 'A'] = false;
        providing[sec - 'A']++;
    }
    cin >> m;
    while (m--) {
        cin >> fir;
        blockSupply(fir - 'A');
    }

    for (int i = 0; i < n; i++)
        if (!cantsupply[i]) ans++;
    cout << ans << '\n';
    return 0;
}